Організація таблиць. Таблиця ідентифікаторів Перевірка правильності семантики і генерація коду вимагають знання характеристик ідентифікаторів, які використовуються у вхідній програмі. Ці характеристики з'ясовуються з описів та з того, як використовуються ідентифікатори у програмі. Зокрема, для імен змінних потрібно знати таку інформацію: тип (цілий, дійсний, символьний тощо); вид (проста змінна, масив, структура тощо); адреса під час виконання програми; вимірність, якщо це ідентифікатор масиву; кількість елементів за відповідним виміром або значення елементів граничних пар; зв'язок з іншими компонентами, якщо розглядається структура або її компоненти; формальний параметр чи ні; якщо формальний параметр, то тип відповідності параметрів; чи оброблявся опис змінної; чи присвоєне значення даній змінній . Для імен процедур важлива інша інформація, а саме: чи є процедура зовнішньою відносно програми; чи є вона функцією; якщо так, то який її тип; чи оброблявся її опис; чи є вона рекурсивною; чи має вона формальні параметри; якщо так, то які саме. Ця інформація накопичується у таблиці ідентифікаторів (таблиці символів, таблиці імен). Тому розглянемо проблему організації таблиць, звертаючи особливу увагу на організацію таблиць символів. Таблиця − це множина записів, організованих таким чином, що кожен запис, а, можливо і його розташування однозначно визначається так званим ключем цього запису. Зазвичай записи складаються з двох полів: ключа, що однозначно визначає цей запис, і тіла запису, що містить власне сам запис. Ідентифікація записів ключами виправдана тим, що тіло запису може мати досить складну структуру, з якої важко виділити єдино можливу ознаку для розпізнавання запису; у той час ключі мають простішу однорідну структуру і допускають порівняння між собою. Ключ повинен бути унікальним, тобто не може бути двох різних записів у таблиці, які мають однакові ключі. Для таблиці ідентифікаторів аргументами таблиці є ідентифікатори, а значеннями їх характеристики. Оскільки кількість літер у ідентифікаторах різна, у аргументі часто записують замість самого ідентифікатора покажчик на нього. Це дає можливість мати аргумент фіксованого розміру. У такому випадку ідентифікатори зберігаються у спеціально відведеній ділянці пам'яті. Кількість літер може зберігатись як частина аргументу або безпосередньо перед ідентифікатором.  Так, таблицю Аргумент Значення можна зберігати так Аргумент Значення або так Аргумент Значення Доступ до тіла запису можна здійснити за ключем запису. Тому, розглядаючи методи роботи з таблицями, основну увагу потрібно приділити обробці ключів (аргументів), тільки при необхідності звертаючись до даних, що знаходяться у тілі (значенні) запису (наприклад, щоб з'ясувати, що певному ключу не поставлені у відповідність дані у полі тіла запису). Операції з таблицями, таким чином, будемо визначати в першу чергу стосовно ключів, хоча вони виконуються і над відповідними тілами записів. Найбільш розповсюдженими операціями над таблицями є: 1) включення нового запису у таблицю; 2) пошук у таблиці запису із заданим ключем; 3) усунення з таблиці запису з вказаним ключем; 4) модифікація запису з вказаним ключем. Ефективність і навіть можливість застосування тої чи іншої операції суттєво залежить від того, яким чином організована таблиця, як вона нарощується, як організовано доступ до окремих записів. Коли компілятор починає трансляцію вхідної програми, таблиця ідентифікаторів порожня або містить декілька елементів для службових слів і стандартних функцій. У процесі компіляції для кожного нового ідентифікатора елемент додається лише один раз. Але для кожного входження ідентифікатора у вхідній програмі здійснюється пошук відповідного елемента у таблиці ідентифікаторів; інформація, отримана при даному входження, співставляється з раніше о...